/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author zhong
 *
 */
public class SentenceSimilarityII {

	public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
		if (words1.length != words2.length) {
			return false;
		}
		HashMap<String, Integer> map = new HashMap<>();
		int idx = 0;
		for (String[] strings : pairs) {
			for (String string : strings) {
				if (!map.containsKey(string)) {
					map.put(string, idx++);
				}
			}
		}
		int[] parent = new int[idx];
		for (int i = 0; i < parent.length; i++) {
			parent[i] = i;
		}
		for (String[] strings : pairs) {
			union(map.get(strings[0]), map.get(strings[1]), parent);
		}
		for (int i = 0; i < words1.length; i++) {
			if (words1[i].equals(words2[i])) {
				continue;
			}
			if (!map.containsKey(words1[i]) || !map.containsKey(words2[i])) {
				return false;
			}
			int i1 = map.get(words1[i]);
			int i2 = map.get(words2[i]);
			if (getRoot(i1, parent) != getRoot(i2, parent)) {
				return false;
			}
		}
		return true;
	}

	private void union(int integer, int integer2, int[] parent) {
		int root1 = getRoot(integer, parent);
		int root2 = getRoot(integer2, parent);
		parent[root1] = root2;
	}

	private int getRoot(int integer, int[] parent) {
		int tmp = integer;
		while (parent[integer] != integer) {
			integer = parent[integer];
		}
		// 把每个路上的节点的父亲设置为根
		while (parent[tmp] != tmp) {
			int tt = parent[tmp];
			parent[tmp] = integer;
			tmp = tt;
		}
		return integer;
	}

	public boolean areSentencesSimilarTwo2(String[] words1, String[] words2, String[][] pairs) {
		if (words1.length != words2.length) {
			return false;
		}
		ArrayList<HashSet<String>> simiWords = new ArrayList<>();
		for (String[] strings : pairs) {
			int i1 = -1, i2 = -1;
			for (int i = 0; i < simiWords.size(); i++) {
				HashSet<String> set = simiWords.get(i);
				if (set.contains(strings[0])) {
					i1 = i;
				}
				if (set.contains(strings[1])) {
					i2 = i;
				}
			}
			if (i1 == -1) {
				if (i2 == -1) {
					HashSet<String> added = new HashSet<>();
					added.add(strings[0]);
					added.add(strings[1]);
					simiWords.add(added);
				} else {
					// 存在i2不存在i1
					simiWords.get(i2).add(strings[0]);
				}
			} else {// 存在i1
				if (i2 == -1) {
					simiWords.get(i1).add(strings[1]);
				} else {
					if (i1 != i2) {// 如果不在同一个列表，需要合并
						simiWords.get(i1).addAll(simiWords.get(i2));
						simiWords.remove(i2);
					}
				}
			}
		}
		for (int i = 0; i < words1.length; i++) {
			String st1 = words1[i];
			String st2 = words2[i];
			if (st1.equals(st2)) {
				continue;
			}
			for (HashSet<String> hashSet : simiWords) {
				boolean s1 = hashSet.contains(st1);
				boolean s2 = hashSet.contains(st2);
				if (s1 != s2) {
					return false;
				}
			}
		}
		return true;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] words1 = "great acting skills".split(" ");
		String[] words2 = "fine painting talent".split(" ");
		String[][] pairs = { { "great", "fine" }, { "acting", "drama" }, { "skills", "talent" } };
		System.out.println(new SentenceSimilarityII().areSentencesSimilarTwo(words1, words2, pairs));
	}

}
